//
// Created by f12160c on 2018/7/26.
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

#include "leetcode/leetcode.hpp"

using namespace std;

class find_helper {
    struct cache_type{
        int count;
        struct cache_type *next[26];
        cache_type() {
            this->count = 0;
            for(int i = 0; i < 26; i++){
                this->next[i] = nullptr;
            }
        }
    };

    struct cache_type *cache;
    int num_char;
public:
    find_helper(vector<string> & words) : cache(new cache_type) {
        this->num_char = 0;
        for(auto word: words){
            auto cache = this->cache;
            for(auto c: word){
                this->num_char++;
                c = c - 'a';
                if(cache->next[c] == nullptr){
                    cache->next[c] = new cache_type;
                }
                cache = cache->next[c];
            }
            cache->count++;
        }
    }

    void free(cache_type *toFree){
        for(int i = 0; i < 26; i++){
            if(toFree->next[i]){
                free(toFree->next[i]);
            }
        }
        delete toFree;
    }
    ~find_helper(){
        free(this->cache);
    }

    bool check(const char *data, int len){
        auto cache = this->cache;

        for(int i = 0; i < len; i++){
            int c = data[i] - 'a';
            if(cache->count){
                cache->count--;
                auto ret = check(&data[i], len - i);
                cache->count++;
                if(ret){
                    return true;
                }
            }
            if(cache->next[c] == nullptr){
                return false;
            }
            cache = cache->next[c];
        }

        if(cache->count == 1) {
            return true;
        }
        else{
            return false;
        }
    }
    vector<int> find(string &s){
        vector<int> ret;
        auto data = s.c_str();
        int len;
        if(s.size() < this->num_char){
            return ret;
        }
        len = s.size() - this->num_char;

        for(int i = 0; i <= len;){
            if(this->check(&data[i], this->num_char)){
                ret.push_back(i);
                i = i + 1;
            }
            else
            {
                i++;
            }
        }
        return ret;
    }
};

vector<int> Solution::findSubstring(string s, vector<string>& words)
{
    find_helper helper(words);
    return helper.find(s);
}

vector<int> Solution::findSubstring_1(string s, vector<string>& words)
{
    unordered_map<string, int> wordmap;
    auto words_len = words.size();
    int word_len;

    vector<int> ret;

    if(words_len == 0){
        return ret;
    }
    word_len = words[0].size();
    for(auto word: words){
        wordmap[word]++;
    }

    for(int i = 0; i < word_len; i++){
        unordered_map<string, int> wordmapTemp;
        int match_count = 0;
        signed int start_index = i;
        for(int j = i; j < s.size();){
            string curr = s.substr(j, word_len);
            if(wordmap.count(curr)){
                if(wordmapTemp[curr] < wordmap[curr]){
                    wordmapTemp[curr]++;
                    match_count++;
                    if( match_count == words_len){
                        ret.push_back(start_index);
                        wordmapTemp[s.substr(start_index, word_len)]--;
                        match_count--;
                        start_index = start_index + word_len;
                    }
                } else {
                    string tmp = s.substr(start_index, word_len);
                    while(tmp != curr){
                        wordmapTemp[tmp]--;
                        match_count--;
                        start_index = start_index + word_len;
                        tmp = s.substr(start_index, word_len);
                    }
                    start_index = start_index + word_len;
                }
            } else {
                if(match_count){
                    wordmapTemp.clear();
                    match_count = 0;
                }
                start_index = j + word_len;
            }
            j = j + word_len;
        }
    }

    return ret;
}